package main

//34. 在排序数组中查找元素的第一个和最后一个位置
func main() {
	nums := []int{5, 7, 7, 8, 8, 10}
	target := 6
	res := searchRange(nums, target)
	for _, num := range res {
		println(num)
	}
}

func searchRange(nums []int, target int) []int {
	badRes := []int{-1, -1}
	if len(nums) == 0 {
		return badRes
	}

	left, right := 0, len(nums)-1
	for left < right {
		mid := (right-left)/2 + left
		midNum := nums[mid]
		if midNum == target {
			left = mid
			break
		}
		if target <= midNum {
			right = mid
		} else {
			left = left + 1
		}
	}

	if nums[left] != target {
		return badRes
	}

	leftIdx, rightIdx := left, left
	for leftIdx > 0 && nums[leftIdx-1] == target {
		leftIdx--
	}

	for rightIdx < len(nums)-1 && nums[rightIdx+1] == target {
		rightIdx++
	}

	return []int{leftIdx, rightIdx}
}

// 34. 在排序数组中查找元素的第一个和最后一个位置
//中等
//相关标签
//相关企业
//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//
//如果数组中不存在目标值 target，返回 [-1, -1]。
//
//你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//
//
//
//示例 1：
//
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
//示例 2：
//
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1]
//示例 3：
//
//输入：nums = [], target = 0
//输出：[-1,-1]
//
//
//提示：
//
//0 <= nums.length <= 105
//-109 <= nums[i] <= 109
//nums 是一个非递减数组
//-109 <= target <= 109
